/*****************************************************************
* Program Assignment :		 AVL树
* Author:             	    @杨领well(blog.csdn.net/yanglingwell)
* Date:               	    2016/11/03  22:00
* Description:
*****************************************************************/

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

const static int LH = 1;  //左子树高
const static int EH = 0;  //平衡
const static int RH = -1;  //右子树高

typedef struct TreeNode
{
	TreeNode* leftChild;   //左孩子
	TreeNode* rightChild;  //右孩子
	int bf;                //平衡因子

	int data;              //数据
} TreeNode, *Tree;

//树的深度
int Height(Tree T)
{
	if (T == NULL) return 0;
	return max(Height(T->leftChild), Height(T->rightChild)) + 1;
}
//计算bf
void CalBF(Tree& T)
{
	T->bf = Height(T->leftChild) - Height(T->rightChild);
}

void RightRotate(Tree& T)
{
	Tree tmp = T;
	T = tmp->leftChild;
	tmp->leftChild = T->rightChild;
	T->rightChild = tmp;

	CalBF(T);
	CalBF(tmp);
}

void LeftRotate(Tree& T)
{
	Tree tmp = T;
	T = tmp->rightChild;
	tmp->rightChild = T->leftChild;
	T->leftChild = tmp;

	CalBF(T);
	CalBF(tmp);
}

//左子树高的调整
void LeftShift(Tree& T)
{
	if (T->leftChild->bf == RH)
	{
		LeftRotate(T->leftChild);
	}
	RightRotate(T);
}
//右子树高的调整
void RightShift(Tree& T)
{
	if (T->rightChild->bf == LH)
	{
		RightRotate(T->rightChild);
	}
	LeftRotate(T);
}
//插入数据
bool insert(Tree& T, int e, bool* isTaller)
{
	if (T == nullptr)
	{
		T = (Tree)malloc(sizeof(TreeNode));
		T->leftChild = NULL;
		T->rightChild = NULL;
		T->data = e;
		T->bf = EH;

		*isTaller = true;
		return true;
	}
	else if (T->data == e)
	{
		*isTaller = false;
		return false;
	}
	else if (T->data > e)
	{
		if (insert(T->leftChild, e, isTaller) == false)
		{
			return false;
		}
		else
		{
			if (*isTaller == true)
			{
				if (T->bf == LH)
				{
					//左边高的调整
					LeftShift(T);
					*isTaller = false;
				}
				else if (T->bf == EH)
				{
					T->bf = LH;
				}
				else
				{
					T->bf = EH;
					*isTaller = false;
				}
			}
			return true;
		}
	}
	else if (T->data < e)
	{
		if (insert(T->rightChild, e, isTaller) == false)
		{
			return false;
		}
		else
		{
			if (*isTaller == true)
			{
				if (T->bf == LH)
				{
					T->bf = EH;
					*isTaller = false;
				}
				else if (T->bf == EH)
				{
					T->bf = RH;
				}
				else
				{
					RightShift(T);
					*isTaller = false;
				}
				return true;
			}
		}
	}
}

//展示
void ShowTree(Tree T)
{
	if (T == NULL)
	{
		cout << "#" << " ";
		return;
	}

	cout << T->data << " ";

	ShowTree(T->leftChild);
	ShowTree(T->rightChild);
}

int main()
{
	Tree T = nullptr;
	bool isTaller;

	for (int i = 0; i < 11; ++i)
	{
		insert(T, i, &isTaller);
	}
	ShowTree(T);


	return 0;
}
